//1.究极笨方法
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret ;
        int n1=nums1.size();
        int n2 = nums2.size();
       
        int i=0,j=0;
        for(;i<n1 && j<n2;) {
            if(nums1[i] >= nums2[j])
                ret.push_back(nums2[j++]);
            else
                ret.push_back(nums1[i++]);

        }
        if(j==n2)
            for(int k =i;k<n1;++k)
                ret.push_back(nums1[k]);

        if(i==n1)
            for(int k =j;k<n2;++k)
                ret.push_back(nums2[k]);
        
        if(ret.size()%2==0)
            return (double)(ret[(ret.size()-1)/2] + ret[(ret.size()-1)/2 + 1])/2;
           
        else
            return ret[ret.size()/2];

    }
};

//2.空间复杂度稍微优化--不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 0 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        int L = m + n;
        int k1 = (L + 1) / 2, k2 = (L % 2 == 0 ? k1 + 1 : k1);

        int i = 0, j = 0, count = 0;
        int v1 = 0, v2 = 0;

        while (count < k2) {
            int val;
            if (i < m && (j >= n || A[i] <= B[j])) {
                val = A[i++];
            } else {
                val = B[j++];
            }
            count++;
            if (count == k1) v1 = val;
            if (count == k2) v2 = val;
        }

        return (k1 == k2) ? v1 : (v1 + v2) / 2.0;
    }
};

//3.log(m+n)


//4.log min{m,n}



